package com.njupt.graphTheory;

import java.sql.Array;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/1/29 20:54
 * @Description: 图的深度优先遍历通过邻接矩阵
 * @Version: 1.0
 */


public class depthFirstTraversal_AdjacencyMatrix {


    public static void dfs(int[][] matrix, int x, int n, List<Integer> result, List<List<Integer>> results) {
        if (x == n) {
            results.add(new ArrayList<>(result));
            return;
        }

        for (int j = 1; j < matrix[0].length; j++) {
            if (matrix[x][j] == 1) {
                result.add(j);
                dfs(matrix, j, n, result, results);
                result.remove(result.size() - 1);
            }
        }
    }

    /**
     * 相当于邻接表法
     * @param matrix
     * @param x
     * @param n
     * @param result
     * @param results
     */
    public static void dfs_lt(int[][] matrix, int x, int n, List<Integer> result, List<List<Integer>> results) {
        if (x == n) {
            results.add(new ArrayList<>(result));
            return;
        }

        for (Integer num : matrix[x]) {
            if(num != null){
                int num_i = num.intValue();
                result.add(num_i);
                dfs_lt(matrix, num_i, n, result, results);
                result.remove(result.size() - 1);
            }


        }
    }


    public static void main(String[] args) {
//        int[][] matrix = {{0, 0, 0, 0, 0, 0},
//                {0, 0, 1, 1, 0, 0},
//                {0, 0, 0, 0, 1, 0},
//                {0, 0, 0, 0, 0, 1},
//                {0, 0, 0, 0, 0, 1},
//                {0, 0, 0, 0, 0, 0}};
//
//        int[][] matrix_lt = {{1,2},
//                {3},
//                {3},
//                {}};
//
//        List<Integer> result = new ArrayList<>();
//        List<List<Integer>> results = new ArrayList<>();
//
//        result.add(0);
//        dfs_lt(matrix_lt, 0 ,3, result, results);
//        System.out.println(results);


        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        //构造邻接矩阵
        int[][] graph = new int[n+1][n+1];
        for (int i = 0; i < m; i++) {
            int s = sc.nextInt();
            int d = sc.nextInt();
            graph[s][d] = 1;
        }

        List<Integer> result = new ArrayList<>();
        List<List<Integer>> results = new ArrayList<>();
        result.add(1);
        dfs(graph,1,n,result,results);

        if(results.isEmpty()){
            System.out.println(-1);
        }

        //结果输出
        for(List<Integer> pa : results){
            for (int i = 0; i < pa.size()-1; i++) {
                System.out.print(pa.get(i) + " ");
            }
            System.out.println(pa.get(pa.size() - 1));
        }


    }
}
